// https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

const int maxn = 5 + 60 << 3;
const int maxm = 5 + 4e5;

int n, m;                  // 数量，容量
vector<vector<int>> v, w;  // 体积，价值权重

int f[maxn][maxm];  // f[i][j] = f[i - 1][j - v[i]] + w[i]

// 读取输入、打包
void init() {
    cin >> m >> n;
    map<int, vector<pair<int, int>>> groups;  // 为每个主件及其附件建立一个 vec
    for (int i = 1; i <= n; ++i) {
        int vi, wi, pi;
        cin >> vi >> wi >> pi;
        // 记得直接计算出物品真实价值
        if (pi > 0) {  // 非主件
            groups[pi].push_back({vi, wi * vi});
        } else {  // 主件
            groups[i].push_back({vi, wi * vi});
            swap(groups[i][0], groups[i].back());  // 主件交换到下标 0 处
        }
    }
    v.push_back(vector<int>()), w.push_back(vector<int>());  // 0 号分组占位
    for (auto &kv : groups) {
        // 将组内的所有组成方式均打包成一个新物品
        v.push_back(vector<int>()), w.push_back(vector<int>());
        // printf("%d: ", kv.first);
        // for (auto tmp : group)
        //     printf("(%d %d), ", tmp.first, tmp.second);
        // puts("");
        auto &group = kv.second;
        // 使用 mask 遍历组员的所有组成方式，注意主件是一定要有的，所以 mask 最低位一定为 1
        for (int mask = 1, ed = 1 << group.size(); mask < ed; mask += 2) {
            // 对于 mask 组成方式，累加其值
            int sv = 0, sw = 0;
            for (int i = 0; i < group.size(); ++i) {
                if ((mask & (1 << i)) == 0) continue;
                sv += group[i].first, sw += group[i].second;
            }
            v.back().push_back(sv), w.back().push_back(sw);
        }
    }
    n = v.size() - 1;  // [1, n] 是各组
    // for (int k = 1; k <= n; ++k) {
    //     printf("%d: ", k);
    //     for (int i = 0; i < v[k].size(); ++i) {
    //         printf("%d %d, ", v[k][i], w[k][i]);
    //     }
    //     puts("");
    // }
}

int main() {
    // input
    init();

    // dp
    for (int k = 1; k <= n; ++k) {
        for (int j = 0; j <= m; ++j) {
            f[k][j] = f[k - 1][j];
            for (int i = 0; i < v[k].size(); ++i) {
                if (j >= v[k][i])
                    f[k][j] = max(f[k][j], f[k - 1][j - v[k][i]] + w[k][i]);
            }
        }
    }
    // for (int k = 1; k <= n; ++k) {
    //     printf("%d: ", k);
    //     for (int j = 0; j <= m; ++j) {
    //         printf("%d ", f[k][j]);
    //     }
    //     puts("");
    // }
    int ans = 0;
    for (int j = 0; j <= m; ++j) {
        ans = max(ans, f[n][j]);
    }
    cout << ans;
}